/**
 * @file DoubleLinkedList.h
 * @brief 双链表模板类的声明和实现
 * @author 侯思睿3190105808
 */

#pragma once
#include <iostream>
#include <iterator>
#include <algorithm>
#include <ostream>

/**
 * @brief 定义一个名称为Node的结构体，链表节点 
 * Node类由所存储的项、指向前一节点的指针、指向下一节点的指针、构造函数组成
 */
template <typename DT>
struct Node  
{
    DT data;   //数据域
    Node *prev;    //前驱指针
    Node *next;    //后继指针

    Node( const DT a = 0, Node *p = nullptr,
        Node *n = nullptr )
        : data{ a }, prev{ p }, next{ n } { }

    Node( DT && a, Node *p = nullptr, Node *n = nullptr )
        : data{ std::move( a ) }, prev{ p }, next{ n } { }      //构造函数
};

/**
 * @brief 一个作为双向链表的List类
 * @tparam DT 
 */
template <typename DT>
class DoubleLinkedList 
{
    public:
	    DoubleLinkedList( DT _val );						            //构造函数
	    DoubleLinkedList( DoubleLinkedList<DT> & L );		            //拷贝构造函数
	    ~DoubleLinkedList( );								            //析构函数
	    void clear( );										            //清空链表
	    int Size( ) const;								                //链表元素个数
	    bool empty( ) { return head->next == head; }		                        //判断链表中是否含有元素
	    Node<DT>* getHead( ) const { return head; }			            //取附加头结点地址
	    void setHead( Node<DT>* ptr ) { head = ptr; }		            //设置附加头结点地址
	    int find( const DT & x );				            //在链表中寻找等于值为x的结点
	    Node<DT>* Locate( int i, int d );						        //在链表中寻找序号为i的结点，d=0从后向前数，d≠0从前向后数
	    bool insert( int i, const DT & x, int d );			            //在第i个结点处插入一个包含值x的新结点，d=0插在前，d≠0插在后
	    void push_back( const DT & x ) { insert( Size( )-1, x, 1 ); }   //在链表末尾插入一个值为x的节点
		void push_front( const DT & x ) { insert( 0, x, 1 ); }          //在链表前端插入一个值为x的节点
	    bool erase( int i, int d );					            //删除第i个结点，d=0从后向前数，d≠0从前向后数
	    void printList( int d );								        //输出，d=0从后向前，d≠0从前向后
    private:
        int theSize;
	    Node<DT>* head;
	    Node<DT>* tail;

	public:
        /**
         * @brief 定义一个常量迭代器
         */
        class const_iterator
        {
            public:
                const_iterator( ) : now{ nullptr }
                    { }

                const DT & operator*( ) const
                    { return retrieve( ); }     //获取当前迭代器的值

                const_iterator & operator++( )
                {
                    now = now->next;
                    return *this;
                }        //重载前向++操作符

                const_iterator operator++( int )
                {
                    const_iterator old = *this;
                    ++( *this );
                    return old;
                }        //重载后向++操作符

                bool operator == ( const const_iterator & rhs ) const
                    { return now == rhs.now; }  //判断迭代器是否相同，即判断指向的节点是否相同
                bool operator!= (const const_iterator &rhs ) const
                    { return !( *this == rhs ); }   //调用==操作符

            protected:
                /**
                 * @brief 存储一个指向“当前”节点的指针作为迭代器单独的数据成员
                 * 标记为protect，使得从const_iterator继承来的类有权访问而其他类无访问权
                 */
                Node<DT> *now;

                DT & retrieve( ) const
                    { return now->data; }

                const_iterator( Node<DT> *p ) : now{ p }
                    { }    //基于指针参数的迭代器构造函数，保证只有List使用

                friend class DoubleLinkedList<DT>;  //friend声明赋予List类访问const_iterator非公有成员的权利
        };

        class iterator : public const_iterator  //继承，iterator就是一个const_iterator
        {
            public:
                iterator( )
                    { }

                DT & operator* ( )
                    { return const_iterator::retrieve( ); }
                const DT & operator* ( ) const
                    { return const_iterator::operator*( ); }

                iterator & operator++ ( )
                {
                    this->now == this->now->next;
                    return *this;
                }

                iterator operator++ ( int )
                {
                    iterator old = *this;
                    ++( *this );
                    return old;
                }
            protected:
                iterator( Node<DT> *p ) : const_iterator{ p }
                    { }

                friend class DoubleLinkedList<DT>;
        };
		/**
         * @brief begin和end返回相应的迭代器
         * @return iterator 
         */
        iterator begin( )
            { return { head->next }; }  //返回一个构造的迭代器,得到迭代器即是得到节点指针
        const_iterator begin( ) const
            { return { head->next }; }
        iterator end( )
            { return { tail }; }
        const_iterator end( ) const
            { return { tail }; }
};

/**
 * @brief Construct a new DoubleLinkedList<DT>:: Double Linked List object
 * 构造函数建立双链表的附加头结点
 * @tparam DT 
 * @param  _val             My Param doc
 */
template <typename DT>
DoubleLinkedList<DT>::DoubleLinkedList( DT _val )
{
	head = new Node<DT>( _val );
	if ( head == nullptr )
	{
		std::cerr << "出错" << std::endl;
		exit( 1 );
	}
	head->next = head->prev = head;
}

/**
 * @brief Construct a new DoubleLinkedList<DT>:: Double Linked List object   拷贝构造函数
 * @tparam DT 
 * @param  L                My Param doc
 */
template <typename DT>
DoubleLinkedList<DT>::DoubleLinkedList( DoubleLinkedList<DT> & L )
{
	DT a;
	Node<DT>* srcptr = L.getHead( );
	Node<DT>* destptr = head = new Node<DT>;
	while ( srcptr->next != L.head )							
	{
		a = srcptr->next->data;
		destptr->next = new Node<DT>( a );
		destptr->next->prev = destptr;
		destptr = destptr->next;
		srcptr = srcptr->next;
	}
	destptr->next = head;
	head->prev = destptr;
}

/**
 * @brief Destroy the DoubleLinkedList<DT>:: Double Linked List object    析构函数
 * @tparam DT 
 */
template <typename DT>
inline DoubleLinkedList<DT>::~DoubleLinkedList( )
{
	clear( );
	delete head;
	delete tail;
}

/**
 * @brief 通过反复删除成员项直至列表为空
 * @tparam DT 
 */
template <typename DT>
inline void DoubleLinkedList<DT>::clear( )
{
	Node<DT>* q;
	while ( head->next != head )
	{
		q = head->next;
		head->next = q->next;
		delete q;
	}
	head->prev = head;
	head->next = head;
}

/**
 * @brief 列表中元素的个数
 * @tparam DT 
 * @return int 
 */
template <typename DT>
inline int DoubleLinkedList<DT>::Size( ) const
{
	Node<DT>* current = head->next;
	int count = 0;
	while ( current != head )
	{
		current = current->next;
		count++;
	}
	return count;
}

/**
 * @brief 寻找其值等于x的节点，若找到，则函数返回该结点地址；否则，返回nullptr
 * @tparam DT 
 * @param  x                My Param doc
 * @return Node<DT>* 
 */
template <typename DT>
int DoubleLinkedList<DT>::find( const DT & x )
{
	Node<DT>* current = head->next;
	int count = 0;
	while ( current != head && current->data != x )
	{
		current = current->next;
		count++;
	}
	if ( current != head ) return count;						
	else return ( -1 );
}

/**
 * @brief 寻找第i个节点，d=0从后向前找d≠0反之。若找到，则函数返回该结点地址；否则，返回nullptr
 * @tparam DT 
 * @param  i                My Param doc
 * @param  d                My Param doc
 * @return Node<DT>* 
 */
template <typename DT>
inline Node<DT>* DoubleLinkedList<DT>::Locate( int i, int d )
{
	if ( head->next == head || i == 0 ) return head;
	Node<DT>* current;
	if ( d == 0 ) current = head->prev;							
	else current = head->next;
	for ( int s = 0; s < i; s++ )									
	{
		if ( current == head ) break;							
		else if ( d == 0 ) current = current->prev;
		else current = current->next;
	}
	if ( current != head ) return current;						
	else return nullptr;									
}

/**
 * @brief 将值为x的新节点插入第i个节点的位置，d=0插在前，反之插在后
 * @tparam DT 
 * @param  i                My Param doc
 * @param  x                My Param doc
 * @param  d                My Param doc
 * @return true 
 * @return false 
 */
template <typename DT>
inline bool DoubleLinkedList<DT>::insert( int i, const DT & x, int d )
{
	Node<DT>* current = Locate( i, d );
	if ( current == nullptr ) return false;
	Node<DT>* newNode = new Node<DT>( x );
	if ( newNode == nullptr )
	{
		std::cerr << "出错！" << std::endl;
		exit( 1 );
	}
	if ( d == 0 )	
	{
		newNode->prev = current->prev;
		current->prev = newNode;
		newNode->prev->next = newNode;
		newNode->next = current;
	}
	else				
	{
		newNode->next = current->next;
		current->next = newNode;
		newNode->next->prev = newNode;
		newNode->prev = current;
	}
	return true;
}

/**
 * @brief 删除第i个节点，d=0从后向前数d≠0反之
 * @tparam DT 
 * @param  i                My Param doc
 * @param  x                My Param doc
 * @param  d                My Param doc
 * @return true 
 * @return false 
 */
template <typename DT>
inline bool DoubleLinkedList<DT>::erase( int i, int d )
{
	Node<DT>* current = Locate( i, d );
	if ( current == nullptr ) return false;
	current->next->prev = current->prev;  
	current->prev->next = current->next; 
	//x = current->data;
	delete current;	
	return true;	
}

/**
 * @brief 输出链表中的元素，d=0正向输出，否则逆向输出
 * @tparam DT 
 * @param  d                My Param doc
 */
template <typename DT>
inline void DoubleLinkedList<DT>::printList( int d )
{
	std::cout << "链表中的元素有： ";
	Node<DT>* current;
	if ( d == 0 ) current = head->prev;
	else current = head->next;
	while ( current != head )
	{
		std::cout << current->data << " ";
		if ( d == 0 ) current = current->prev;
		else current = current->next;
	}
	std::cout << std::endl;
}



/**
 * 注：使用了附加头结点，方法和代码的参考内容如下
 * https://blog.csdn.net/qq_43650934/article/details/109824171
 * https://blog.csdn.net/dream_of_grass/article/details/120480512
 * https://wenku.baidu.com/view/83834d3356270722192e453610661ed9ad5155fb.html
 */
